package _2022.hot100._78_子集;

import java.util.ArrayList;
import java.util.List;

/**
 * @author： YHSimon
 * @date： 2022-04-18 15:08
 */
public class Solution {
    public List<List<Integer>> subsets(int[] nums){
        List<List<Integer>> combinations=new ArrayList<>();
        List<Integer> combination=new ArrayList<>();
//        dfs(nums,0,combination,combinations);
        backtrack(nums, 0, combination, combinations);
        return combinations;
    }

    private void dfs(int[] nums, int index, List<Integer> combination, List<List<Integer>> combinations) {
        if(index==nums.length){
            combinations.add(new ArrayList<>(combination));
            return;
        }
        combination.add(nums[index]);
        dfs(nums, index+1, combination, combinations);

        combination.remove(combination.size()-1);
        dfs(nums, index+1,combination , combinations);
    }

    public void backtrack(int[] nums, int index, List<Integer> combination, List<List<Integer>> combinations){
        combinations.add(new ArrayList<>(combination));
        for(int i=index;i<nums.length;i++){
            combination.add(nums[i]);
            System.out.println("递归前==》"+combination.toString()+"index="+index);
            backtrack(nums, i+1, combination, combinations);
            System.out.println("递归后==》"+combination.toString()+"index="+index);
            combination.remove(combination.size()-1);
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.subsets(new int[]{1,2,3}).toString());
    }
}
